package com.aurora.leetcode.answer;

import java.util.ArrayList;
import java.util.List;

public class ValidParenthese_20 {
    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     */

    public static boolean isValid(String s) {
        if (s.length() == 1 || s.length() % 2 != 0) return false;
        int mid = (s.length() - 1) / 2;
        List<Character> parenthese = new ArrayList<>();
        int right = -1;
        for (int i = 0; i < s.length(); ++i) {
            char symbol = s.charAt(i);
            if (symbol == '(' || symbol == '[' || symbol == '{') {
                parenthese.add(symbol);
                right++;
                if (right > mid) return false;
            } else {
                if (right < 0) return false;
                boolean flag = true;
                switch (symbol) {
                    case ')':
                        if (parenthese.get(right) != '(')
                            flag = false;
                        break;
                    case ']':
                        if (parenthese.get(right) != '[')
                            flag = false;
                        break;
                    case '}':
                        if (parenthese.get(right) != '{')
                            flag = false;
                        break;
                }
                if (flag) {
                    parenthese.remove(right);
                    right--;
                } else {
                    return false;
                }

            }
        }
        return parenthese.size() == 0 ? true : false;
    }

    public static void main(String[] args) {
        String s1 = "(";
        String s2 = "([";
        String s3 = "([}";
        String s4 = "([]";
        String s5 = "([])";
        System.out.println(isValid(s1));
        System.out.println(isValid(s2));
        System.out.println(isValid(s3));
        System.out.println(isValid(s4));
        System.out.println(isValid(s5));
    }
}